/*
题目: 重排链表
给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

https://leetcode.cn/problems/reorder-list
 */
public class ReorderList {
    public void reorderList(ListNode head) {
        ListNode ret = head;
        ListNode fast = head.next;
        ListNode slow = head;

        // 找到中点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 反转后半段
        ListNode cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        // 至此, slow 到达最后一个节点

        // 开始正式连接
        ListNode tail = slow;
        cur = head;
        // 头尾 指针都不为 空
        while (cur != null && tail != null) {
            ListNode t1 = cur.next;
            ListNode t2 = tail.next;
            cur.next = tail;
            tail.next = t1;

            cur = t1;
            tail = t2;
        }
    }
}
